package leetcode._041;
/**
 * Title: 41. First Missing Positive
 */

/**
 * Given an unsorted integer array, find the smallest missing positive integer.
 *
 * Example 1:
 *
 * Input: [1,2,0]
 * Output: 3
 * Example 2:
 *
 * Input: [3,4,-1,1]
 * Output: 2
 * Example 3:
 *
 * Input: [7,8,9,11,12]
 * Output: 1
 *
 * Input: [7,8,9,11,13]
 * Output:1
 *
 * Input:[5,2,2,4,1,-1]
 * Output:3
 * Note:
 *
 * Your algorithm should run in O(n) time and uses constant extra space.
 */

/**
 * https://leetcode.com/problems/first-missing-positive/
 * 找出最小的缺失的最小非正数
 *
 * Runtime: 6 ms, faster than 5.88% of Java online submissions for First Missing Positive.
 * Memory Usage: 35.9 MB, less than 100.00% of Java online submissions for First Missing Positive.
 * 第一步将负数移动最左边
 * 
 */
public class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0) {
            return 1;
        }
        if (nums.length == 1) {
            if (nums[0] != 1) {
                return 1;
            } else {
                return 2;
            }
        }
        int noPositiveIntegerCount = moveNoPostiveToRight(nums);;
        if (noPositiveIntegerCount == nums.length) {
            return 1;
        }
        int nextMin = 0;
        int minCount = getMinCount(nums, 0, nums.length - noPositiveIntegerCount);
        int min = nums[0];
        if (min > 1) {
            return 1;
        }
        while (noPositiveIntegerCount < nums.length) {
            moveToRight(nums, minCount, nums.length - noPositiveIntegerCount);
            noPositiveIntegerCount += minCount;
            minCount = getMinCount(nums, 0, nums.length - noPositiveIntegerCount);
            nextMin = nums[0];
            System.out.println("min " + min + " nextMin " + nextMin);
            if (nextMin - min > 1) {
                return min + 1;
            }
            if (nextMin == min) {
                return min + 1;
            }
            min = nextMin;
        }
        return 0;
    }

    /**
     * 移动非正数到右边，并返回非正数的个数
     * @param nums
     * @return
     */
    private int  moveNoPostiveToRight(int[] nums) {
        int noPositiveIntegerCount = 0;
        int length = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0 && length - i > noPositiveIntegerCount) {
                int temp = nums[i];
                noPositiveIntegerCount ++;
                int tempSwap = nums[length - noPositiveIntegerCount];
                nums[i] = tempSwap;
                nums[length - noPositiveIntegerCount] = temp;
                i--;
            }
        }
        return noPositiveIntegerCount;
    }

    /**
     * 再到在[left,right)区间的最小值的个数，最小值是第0个元素
     * @param nums
     * @param left
     * @param left
     * @return
     */
    public int getMinCount(int []nums, int left, int right) {
        int countMin = 0;
        int min = Integer.MAX_VALUE;
        for (int i = left; i < right; i ++) {
            if (nums[i] <= min) {
                min = nums[i];
            }
        }
        for (int i = left; i < right; i ++) {
            if (nums[i] == min) {
                countMin ++;
                int tempLast = nums[left + countMin - 1];
                nums[i] = tempLast;
                nums[left + countMin - 1] = min;

            }
        }
        return countMin;
    }

    private void moveToRight(int []nums, int count, int lastPos) {
        for (int i = 0; i < count; i++) {
            int temp = nums[lastPos - i  - 1];
            int tempHeader = nums[i];
            nums[i] = temp;
            nums[lastPos - i - 1] = tempHeader;
        }
    }
}
